package huisu;
//N皇后问题
public class NQueens {

	public static void main(String[] args) {
		System.out.println(getNum(4));
	}
	//两个皇后不能在同一行，同一列，对角线（主或者副）
	public static int getNum(int n){
		//n皇后问题只有n == 1 或者 n >= 4的时候才有解
		if(n < 1 || n == 2 || n == 3){
			return 0;
		}
		int[] record = new int[n];  //用来记录每一行所放置的皇后所在的列
		int result = realSolve(0, record, n);
		return result;
	}
	
	public static int realSolve(int i, int[] record, int n){
		//当放置到第n行时，加1
		if(i == n){
			return 1; 
		}
		int res = 0;
		for (int j = 0; j < n; j++) {
			//判断是否可以放置
			if(isValid(record, i, j)){
				record[i] = j;
				System.out.println("i: " + i + " j: " + j );
				res += realSolve(i + 1, record, n);
			}
		}
		return res;
	}
	
	//判断第i行放置在第j列是否是有效的
	public static boolean isValid(int[] record, int i, int j){
		//遍历0 --- i
		for (int k = 0; k < i; k++) {
			if(j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)){
				return false;
			}
		}
		return true;
	}
	
	
	//使用位运算来进行加速 
	public static int getNum2(int n) {
		if(n < 1 || n == 2 || n == 3){
			return 0;
		}
		if(n > 32){
			System.err.println("sorry, the n is bigger than 32");
			return -1;
		}
		//-1 的补码全是1， (1 << n) - 1  将 n  位全变为1
		//record de 32位中1表示可以放置，0不能放置
		//对于4皇后问题，初始为0....01111
		int initialLim = n == 32 ? -1 : (1 << n) - 1;
		int result = realSolve2(initialLim, 0, 0, 0);
		return result;
	}
	
	//col表示哪些列已经放置了皇后，1代表已经放置，0代表没有放置
	//left表示递归计算到上一行为止，受已经放置的所有皇后的副对角线的影响，导致当前行不能放置皇后，1代表不能放置，0可以
	//left每左移一位，就可以得到之前所有皇后的副对角线对当前行的影响
	//right....主对角线的影响，1代表不能放置，0可以
	//right每右移一位，就可以得到之前所有皇后的对角线对当前行的影响
	public static int realSolve2(int initialLim, int col, int left, int right){
		if(col == initialLim){
			return 1;
		}
		int pos = 0;
		int mostRightOne = 0;
		pos = initialLim & (~ (col | left | right));
		int res = 0;
		while(pos != 0){
			mostRightOne = pos & (~ pos + 1);
			pos = pos - mostRightOne;
			res += realSolve2(initialLim, col | mostRightOne, 
					(left | mostRightOne) << 1, (right | mostRightOne) >>> 1);
		}
		return res;
	}
}
